Boyer–Moore majority vote algorithm

Boyer–Moore majority vote algorithm is an algorithm that finds the majority element and its count from a given sequence in O(N)TIME O(1)SPACE.

Pseudocode

• Initialize an element m and a counter i with i = 0
• For each element x of the input sequence:
  • If i = 0, then assign m = x and i = 1
  • else if m = x, then assign i = i + 1
  • else assign i = i − 1
• Return m
  初始化major元素 major = arr[0]，counter = 1
  遍历序列中每个元素 1:end
  if counter == 0 reset: major to be current pointer and counter to be 1
  else if major == current element increment counter
  else (current element is not major and counter need not to be reset) decrement counter

Example

Leetcode 169
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

class Solution {
    public int majorityElement(int[] num) {
        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
        }
        return major;
    }
}

Reference:
https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm
https://www.zhihu.com/question/49973163/answer/235921864

打赏